package backtrack

var dirs = [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	vis := make([][]bool, m)
	for i := range vis {
		vis[i] = make([]bool, n)
	}
	var dfs func(i, j, k int) bool 
	dfs = func(i, j, k int) bool{
		if board[i][j] != word[k] {
			return false
		}
		if k == len(word) - 1 {
			return true
		}
		vis[i][j] = true
		defer func() {
			vis[i][j] = false
		}()
		for _, dir := range dirs {
			if newI, newJ := i + dir[0], j + dir[1]; 0 <= newI && newI < m && 0 <= newJ && newJ < n && !vis[newI][newJ] {
				if dfs(newI, newJ, k + 1) {
					return true
				}
			}
		}
		return false
	}

	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if dfs(i, j, 0) {
				return true
			}
		}
	}
	return false
}